阅读笔记：Multi-Task Allocation in Mobile Crowd Sensing with Mobility Prediction
一、基本信息
- 阅读人和日期：WP Zhu，2022.4.22
- 引用格式：Zhang, J., & Zhang, X. (2021). Multi-Task Allocation in Mobile Crowd Sensing with Mobility Prediction. IEEE Transactions on Mobile Computing.
- 单位：South China University of Technology.
- 原文链接： https://ieeexplore.ieee.org/document/9451627
- 概述：本文根据参与者的轨迹，采用了基于模糊控制理论预测参与者完成任务的概率，并提出了基于贪心策略和基于粒子群优化的任务分配算法进行任务分配，目的是为了在总体预算和参与者最大工作负载的限制下，最大化总体的任务完成概率。
二、动机及创新点
动机：
仅仅采用概率理论来刻画参与者的轨迹无法全面地对其进行预测，因为现实中可能会存在一些不确定因素导致参与者的轨迹会出现波动(如出现堵车)，或者在参与者经常走的路线他们可能愿意走快一点赶到任务地点去完成任务，使得他们也可以成为完成任务的候选人(如果仅用概率论，根据常规路线预测，规定时间不在任务地点就无法成为候选人)。
主要贡献及创新点：
首先，提出了基于模糊控制理论的轨迹预测方法(FCSMP)；其次，在轨迹预测的基础上，提出了基于贪心策略的任务分配方法(MLF)；进一步地，提出了基于粒子群优化的任务分配算法(GGPSO)，提高任务分配的性能。
三、问题描述和方法论
1.参与者轨迹预测公式：
2. 任务完成概率：
3. 目标函数及限制条件：
在感知成本和参与者最大工作负载的限制下，最大化任务完成的概率，问题形式化如下所示：
四、算法设计
1.轨迹预测模型FCSMP
分为以下三个步骤：
模糊化：输入参与者达到位置的时间和感知时间，对其进行模糊度衡量。其中，参与者到达时间分为非常早到、早到、刚刚好到、晚到、非常晚到五个状态，感知时间分为短时间、中等时间、长时间三个状态。
模糊推断：根据模糊化的结果，计算参与者完成感知任务模糊值，采用IF-THEN规则将结果分为几乎不可能、不可能、可能、很有可能、极有可能五种状态。
解模糊化：根据模糊推断的模糊值，计算参与者完成任务的概率。
2.基于贪心策略的分配算法(MLF)
在满足预算限制和最大工作负载的参与者候选集中，优先选择完成概率最大的参与者，算法伪代码如下所示：
３. 基于粒子群优化的任务分配算法(GGPSO)
采用算法1中的方法对粒子进行初始化，然后采用离散粒子群优化算法，引入遗传算法中的变异和交叉操作，进一步提高任务整体的完成概率，算法伪代码如下所示：
五、实验部分
1. 数据集：
采用了San Francisco轨迹数据集和GeoLife轨迹数据集
2. 基准算法：
轨迹预测方法：基于概率统计预测方法(MPP)、引入泊松分布的概率统计(MPPo)
任务分配方法：传统遗传算法(GA)、传统粒子群优化算法(PSO)、改进版的遗传算法(GMWS)、婚姻匹配算法(GSMS).
3. 实验结果：
首先，考虑相同任务分配算法(GGPSO)，不同轨迹预测模型对结果的影响，结果如下图所示：
上图从任务数、参与者任务、总体预算三个方面衡量它们对结果的影响，从两个数据集中可以看出，在本文中设计的FCSMP预测模型下获得的整体性能优于其他预测算法。
其次，考虑相同轨迹预测模型(FCSMP)，不同任务分配算法对结果的影响，结果如下图所示：
从上图可以看出，本文提出的基于粒子群优化的任务分配算法能够获得较优的性能。